package leetcode_900;

/**
 *@author 周杨
 *DecodedStringAtIndex_880_ 给定一个压缩过的字符串 问第K个位置的元素是什么
 *describe:很好的题目 利用栈的思想 重复的元素不必计算  AC 76%
 *2018年11月8日 下午3:54:08
 */
public class DecodedStringAtIndex_880_ {
	public static void main(String[] args) {
		DecodedStringAtIndex_880_ test=new DecodedStringAtIndex_880_();
		System.out.println(test.decodeAtIndex("y959q969u3hb22odq595"
				,222280369));
	}
	
	public String decodeAtIndex(String S, int K) {
        long size = 0;
        int N = S.length();

        //最多循环100次 算出这个字符串最终长度 其实前面都是重复的
        for (int i = 0; i < N; ++i) {
            char c = S.charAt(i);
            if (Character.isDigit(c))
                size *= c - '0';
            else
                size++;
        }
        for (int i = N-1; i >= 0; --i) {
            char c = S.charAt(i);
            K %= size;//1:K 此时还大于size 那么就有很多重复的
            if (K == 0 && Character.isLetter(c))
                return Character.toString(c);
            if (Character.isDigit(c))
                size /= c - '0';
            else
                size--;
        }
        throw null;
    }
	
	/**
	 * describe:常规方法  空间超时
	 * 2018年11月8日 下午2:59:11
	 */
	public String decodeAtIndex1(String S, int K) {
		int index=0;
        StringBuilder sb=new StringBuilder();
        while(sb.length()<K) {
        	char now=S.charAt(index++);
        	if(now<='z'&&now>='a') {
        		sb.append(now);
        	}
        	else {
        		String old=sb.toString();
        		for(int i=1;i<now-'0';++i) {
        			sb.append(old);
        		}
        	}
        }
        return String.valueOf(sb.charAt(K-1));
    }
}
